前言

八月底得知接下來的google on-site 面試要面L5 level的
跟HR敲了約一個月的準備時間 於九月底會正式開始面試
剛好於鐵人賽的時間疊合
就來當寫個筆記記錄一下整個過程 包含被刷掉的過程...

面試流程

3 x Coding, Data Structures & Algorithms
1 x Large Scale Backend System Design
1 x Googleyness and Leadership (Non-technical)

看起來最先要準備的是演算法跟資料結構

準備方向

Arrays
Trie, segment trees/fenwick trees, bitmask
lists, maps, stacks, priority queues, binary trees, graphs, bags, and sets.
Linked list, stacks, queues, two pointers/sliding window
Binary search
BFS/DFS/Flood fill
Tree traversals
Hash tables/maps/sets
Binary heaps
Dynamic programming
Union find
Ad hoc/string manipulations
Sorting
Dijkstra, greedy algorithms, divide and conquer, dynamic programming, recursion, brute force search.

刷題囉

不用加號的加法

一個函示不利算數運算子可以將兩個數字相加

方向:
We can use bitwise operator to do it.
eg. 2 + 2 = 010 + 010 = 100

for add part
1 1 = 0
0 0 = 0
0 1 = 1
1 0 = 1

we can think about xor (^) (a^b)

for carry part
1 1 = 10
0 1 = 00
1 0 = 00
0 0 = 00

we can think abount and (&) then move left 1 bit ( << 1)

e.g. 10 + 8 = 1010 + 1000 -> add part(0010) + carry part(10000)

int add(int a, int b) {
    if (b == 0) {
        return a;
    }
    int sum = a ^ b;
    int carry = (a & b) << 1;
    return add(sum, carry);
}

Sliding Window Maximum

Q: https://leetcode.com/problems/sliding-window-maximum/

key point:
use queue to record k nums, and the let the first element is max element

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {   
        if (k <= 0) return new int[0];
        if (nums == null || nums.length <= 1 || k == 1) return nums;
        
        Deque<Integer> deque = new ArrayDeque<>(k);
        int[] output = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            cleanDeque(deque, nums, i, k);
            deque.addLast(i);
            if (i - k + 1 >= 0) output[i - k + 1] = nums[deque.getFirst()];
        }
        return output;
    }
    
    private void cleanDeque(Deque<Integer> deque, int[] nums, int i, int k) {
        if (!deque.isEmpty() && deque.getFirst() < i - k + 1) deque.removeFirst();
        while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) deque.removeLast();
    }
}

Candy

Q: https://leetcode.com/problems/candy/

Brute Force

To do this operation again and again to find the result.

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        boolean hasChanged = true;
        while (hasChanged) {
            hasChanged = false;
            for (int i = 0; i < ratings.length; i++) {
                if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    hasChanged = true;
                }
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    hasChanged = true;
                }
            }
        }
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}

Using two arrays

find left max array and right max array, then mix them to find the max candy we need.

public class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int[] left2right = new int[ratings.length];
        int[] right2left = new int[ratings.length];
        Arrays.fill(left2right, 1);
        Arrays.fill(right2left, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left2right[i] = left2right[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right2left[i] = right2left[i + 1] + 1;
            }
        }
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(left2right[i], right2left[i]);
        }
        return sum;
    }
}

Trapping Rain Water

Q: https://leetcode.com/problems/trapping-rain-water/

use two array to record left and right height, to find the min height for height[i]

class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int result = 0;
        leftMax[0] = height[0];
        for (int i = 1;i < height.length;i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2;i >= 0;i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
        for (int i = 0;i < height.length;i++) {
            result += (Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return result;
    }
}

Tips:
遇到兩邊界值的問題時，使用兩個陣列分別對左邊界及右邊界做處理，在合併查詢可以有效解決問題。